The present invention relates to methods of producing optimized designs using a computer system by controlling the operation of a hierarchy or sequence of applications of design optimization programs, design quality estimation programs and value computation programs. In particular these methods can be used to produce designs useful for developing machinery, articles of manufacture, compositions of matter, thereof.
An important characteristic of stochastic optimization methods, such as simulated annealing, genetic algorithms and multi-start hill climbing, is that they can be run again and again on the same inputs, each time potentially producing a different answer. Some of the answers will be better, some worse. Indeed, it is common to run such algorithms a few times, and to use the best of the answers produced. The difficulty is in determining how many times.
The issue is complicated by the fact that in many cases the output of the optimizer is not a final artifact. Rather, the design task at hand is being done in a series of stages, or levels of abstraction, and the output of one optimizer is in turn used as input to another stage of design. For example, in designing a microprocessor, we might start with an instruction set, implement that as a set of register transfers, implement the register transfers as boolean logic, implement the boolean logic as a xe2x80x9cnet listxe2x80x9d defining how specific circuit modules are to be wired together, implement the net list by choosing specific locations for the circuit modules and wires on the surface of a VLSI chip, etc. Thus, if several consecutive levels of design are to be done by stochastic methods, we really have a tree of alternate designs, whose leaves are the final, concrete designs, and whose internal nodes are designs at intermediate levels.
Each time an optimizer at any level gives us an output, the skilled artisan faces a choice of what to do next. The question is whether one should declare the best design one has so far at this level to be xe2x80x9cgood enoughxe2x80x9d and proceed to use it as input to the next level, or whether one should rerun the optimizer in hopes of getting a better design at the current level, or whether one should go back up to some higher level in the tree and try again there.
Current practice is often to use a xe2x80x9cwaterfallxe2x80x9d approach, i.e. run the optimizer at one level some number of times, choose the best result, and proceed forwards. This would be an optimal approach if one had a completely accurate way of evaluating designs at intermediate levels (i.e., evaluating how good a final design one will get from this intermediate design), but in practice all one normally has are heuristics that tell us approximately how good an intermediate design is. In order to tell, e.g., which of two intermediate designs is actually better, we may have to try generating one or more designs at the next level from each of them.
The present invention presents an alternative to the waterfall method, which we call xe2x80x9crational best firstxe2x80x9d (RBF) search, that is capable of doing this kind of exploratory design. We will describe RBF and present empirical data from one example design task showing that RBF can be a large improvement over waterfall search.
The key insight behind RBF is that a good control method is not one that finds the best design (since finding the absolute best design takes exponential time), but one that gives the best tradeoff between computation cost and design quality, and that therefore control decisions should be based on an analysis of the utility and the cost of each possible action.
In order to define the value, i.e. the utility, of running an optimizer, we have to define the value of the designs it produces. We will assume that we are given the values of the ground level objects, in the form of a function that maps an object""s score into its value. We define the value of an intermediate level design to be the profit we will get from using that design as a starting pointxe2x80x94i.e., the expected value of the final ground level design it will lead to, minus the expected cost of the computation needed to go from that intermediate level design to the final design.
Using this definition of value allows us to compare two designs that are at different levels of abstraction, and leads to a simple heuristic: always work on the design with the highest estimated profit, at whatever level it is on. Of course, to make this operational we need a way to estimate the profit inherent in an intermediate-level design, but it turns out that we can use the ground level values and some fairly simple statistical reasoning to do so.
One embodiment of the invention includes: A method for controlling a hierarchy or sequence of applications of design optimization programs, design quality estimation programs and value computation programs, in a computer system to improve the tradeoff between quality of a final design result and computation time expended in the optimization programs to get that result, each design optimization program in the sequence taking as input the previous design program""s result; a first design optimization program taking as input one or more specifications of an overall design task and a last program producing as output a complete design result for said task; said method including the steps of:
1. inputting said one or more specifications of said overall design task and initializing a set of design objects to include at least said one or more specifications;
2. computing the initial estimate of the utility of designing from said specifications using said design optimization programs, said utility being defined as the average value of the final result of a design process starting with said specification, minus the average cost in computer time of said design process; wherein each of said optimization programs when run multiple times will produce different intermediate design results of varying quality as measured by said design quality estimation programs, and each of said optimization programs having a known or estimated cost in computer time per run, said value computation program taking as data the design quality of the overall design result of the overall design task as measured by the design quality estimation programs, and producing as output a value to the user of said overall design result in comparable units to the known or estimated costs of running said optimization programs;
3. choosing as a current design object from the set of design objects, the design object whose estimated utility is greatest; examining and recognizing if said current design object is a complete design result for the overall design task, and if so producing an output of said current design object as the final design result of the overall design task, and if not proceeding to step 4;
4. Running the appropriate optimization program with said current design object as input to produce a new design object as a result, running an appropriate design quality estimation program on said new design object, estimating the utility as defined above of said new design object, and adding said new design object to said set of design objects;
5. Revising the estimate of utility for the current design object based on the quality of the new design object, and revising the utility estimates of all ancestor design objects from which the current design object was derived, based on the revised utility estimate of the current design object; and repeating from step 3.
In another embodiment of the invention, the method includes computation of the utility of a new design object that is a complete design result for the overall design task by running the value computation program on the new design object.
In another embodiment of the invention the method includes applying a specific algorithm when computing the utility of the new design object that is not a complete design result for the overall design task. The conditions and algorithms applied in such an instance are:
Compute the threshold score, stn(sp), for generating children objects at level n from a parent object at level n+1 whose score is sp, to be such that             ∑              s         less than                               s            t            n                    ⁢                      (                          s              p                        )                                ⁢                  (                                            V              n                        ⁢                          (              s              )                                -                                    V              n                        ⁢                          (                                                s                  t                  n                                ⁢                                  (                                      s                    p                                    )                                            )                                      )            ⁢                        CSDP                      n            +            1                          ⁢                  (                                    s              p                        ,                          s              c                                )                      =      c    n  
Whereby n is the level of the new design object, where levels are numbered so that level 0 includes the complete design results for the overall design task, and objects at level n are generated from objects at level n+1; whereby s ranges over possible scores of level n objects; whereby CSDPn+1(Sp, Sc) is an estimate of the probability that a design object generated from a design object at level n+1 will have score Sc, given that the object at level n+1 had score Sp.; whereby cn is the cost of running the design optimization program that generates designs at level n, whereby Vn(s) is the utility of a design at level n whose score is s; and compute the utility of the new design object at level n+1 according to the formula Vn+1(sp)=Vn(stn(sp)).
A further embodiment of the invention includes a step of estimating the utility of design objects based on initially estimating the probability distribution of scores of the children of said design object from the score of said design object, and revising said estimate of the probability distribution of scores of the children of said design object based on the scores of such children as are actually generated. The estimates of the probability distribution of scores of the children of a design object are made according to the following formulas:             RD      parent                        xe2x80x83                ⁢                  n          +          1                      ⁡          (      R      )        =                              RDS                      s            p                                              xe2x80x83                        ⁢                          n              +              1                                      ⁡                  (          R          )                    ⁢                        ∏                      i            =                          xe2x80x83                        ⁢                          1              ⁢              …              ⁢                              xe2x80x83                            ⁢              n                                      ⁢                  xe2x80x83                ⁢                              CSDR            R                                          xe2x80x83                            ⁢                              n                +                1                                              ⁡                      (                          s              i                        )                                      ∫                                    RDS                          s              p                                                      xe2x80x83                            ⁢                              n                +                1                                              ⁡                      (            R            )                          ⁢                              ∏                          i              =                              1                ⁢                …                ⁢                                  xe2x80x83                                ⁢                n                                              ⁢                      xe2x80x83                    ⁢                                                    CSDR                R                                                      xe2x80x83                                    ⁢                                      n                    +                    1                                                              ⁡                              (                                  s                  i                                )                                      ⁢                          ⅆ              R                                          
whereby the child score distributions of the various design objects at any given level are approximated by a parameterized family of distributions CSDRR(s); whereby R is the parameter or list of parameters characterizing a specific distribution from said family of distributions and CSDRR(s)=P(child score=s) is the specific distribution of child scores, given R; whereby RDSspn+1(R) is a function giving an initial estimate of the probability that R is the correct value of the parameter characterizing the child score distribution of a level n+1 design object, based on the score sp of said level n+1 object; whereby the scores si, i=1 to n, are the scores of the children that have actually been generated; and whereby RDparentn+1(R) is the revised estimate of the probability that R is the correct value of the parameter characterizing the child score distribution of a parent design object at level n+1 based on both the score sp of said level n+1 design object and the scores si,             CSD      parent              n        +        1              ⁢          (      s      )        =            ∫      R        ⁢                            RD          parent                                    xe2x80x83                        ⁢                          n              +              1                                      ⁢                  (          R          )                    ⁢                        CSDR          R                                    xe2x80x83                        ⁢                          n              +              1                                      ⁢                  (          s          )                    ⁢              ⅆ        R            
whereby CSDparentn+1(s) is the child score distribution of said level n+1 design object.
In a further embodiment of the invention there is included a computer generated design for a machine, an article of manufacture or a composition of matter, said design made by a process which controls a hierarchy or sequence of design optimization programs, design quality estimation programs and value computation programs, said process including the steps of:
1. inputing said one or more specifications of said overall design task and initializing a set of design objects to include at least said one or more specifications;
2. computing the initial estimate of the utility of designing from said specifications using said design optimization programs, said utility being defined as the average value of the final result of a design process starting with said specification, minus the average cost in computer time of said design process; wherein each of said optimization programs when run multiple times will produce different intermediate design results of varying quality as measured by said design quality estimation programs, and each of said optimization programs having a known or estimated cost in computer time per run, said value computation program taking as data the design quality of the overall design result of the overall design task as measured by the design quality estimation programs, and producing as output a value to the user of said overall design result in comparable units to the known or estimated costs of running said optimization programs;
3. choosing as a current design object from the set of design objects, the design object whose estimated utility is greatest; examining and recognizing if said current design object is a complete design result for the overall design task, and if so producing an output of said current design object as the final design result of the overall design task, and if not proceeding to step 4;
4. Running the appropriate optimization program with said current design object as input to produce a new design object as a result, running an appropriate design quality estimation program on said new design object, estimating the utility as defined above of said new design object, and adding said new design object to said set of design objects;
5. Revising the estimate of utility for the current design object based on the quality of the new design object, and revising the utility estimates of all ancestor design objects from which the current design object was derived, based on the revised utility estimate of the current design object; and repeating from step 3.